package edu.cmu.cs211.pg.algorithms;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Set;
import java.util.Stack;
import java.util.TreeSet;

import edu.cmu.cs211.pg.graph.Edge;
import edu.cmu.cs211.pg.graph.Graph;
import edu.cmu.cs211.pg.graph.MyDirectedGraph;
import edu.cmu.cs211.pg.graph.Path;
import edu.cmu.cs211.pg.graph.WeightedEdge;

public class MstTspApproximation<V extends Comparable<V>>
{
    private Dijkstra dijkstra;
    private Kruskal kruskal;
    private Graph<V, WeightedEdge<V>> k;
    private Graph completeG;
    private Graph<V, WeightedEdge<V>> original;
    
    protected MstTspApproximation(){}
    
    public MstTspApproximation(Kruskal kruskal, Dijkstra dijkstra)
    {
        this.kruskal = kruskal;
        this.dijkstra = dijkstra;
    }
    
    /**
     * Generates a tour of a specified set of nodes in the graph using the
     * MST-TSP 2-competitive approximation algorithm.
     * 
     * In order to aid in the unit testing of this class, we require
     * that the order you visit neighbors in the DFS portion of
     * the algorithm is the same as the natural ordering of the vertex
     * type V. You should also use the instances of Kruskal and
     * Dijkstra passed into the constructor of this class, not your own.
     * 
     * @param g the graph to generate the tour on. This UNDIRECTED
     *          graph may not be complete, but must be connected.
     *          
     * @param verts the vertices in the graph that you want to tour.
     *              This may be a subset of the vertices in the graph.
     *                       
     * @param start the vertex at which the tour must begin and end.
     *        start may not be in the set of vertices to tour, but
     *        your tour must begin and end at start.
     * 
     * @throws IllegalArgumentException if any of the vertices in the
     *              verts set are not in the graph. 
     * @throws NullPointerException if g, verts, or start are null
     * 
     * @return A list of vertices representing the order you would visit
     *         vertices in the original graph such that every vertex in
     *         the specified verts set is visited at least once.
     */
    public List<V> approximateTour(Graph<V,WeightedEdge<V>> g, Set<V> verts, V start)
    {
        /*
         * check to make sure that nothing is null
         */
        if (g == null || verts == null || start == null) throw new NullPointerException();
        
        /*
         * checks to see if any of the vertices in the verts set are not in the 
         * graph.
         */
        original = g;
        Set verticesInGraph = g.vertices();
        Iterator iVerts = verts.iterator();
        while (iVerts.hasNext()) {
            V v = (V) iVerts.next();
            if (!verticesInGraph.contains(v)) throw new IllegalArgumentException();
        }
        
        /*
         * check to see if the graph is connected
         */
        ArrayList list = new ArrayList();
        Iterator igraph = verticesInGraph.iterator();
        while(igraph.hasNext()) {
            V v = (V) igraph.next();
            if(g.outgoingNeighbors(v) == null) 
                list.add(v);
        }
        
        List<V> retList = new ArrayList<V>();
        
        //k = kruskal.spanningTree(g);
        
        Stack<Node> stack = new Stack<Node>();
        
        /*
         * connected complete graph
         */
        
        completeG = new MyDirectedGraph<V, WeightedEdge<V>>(verts);
        Set<V> newVerts = verts;                //creates a new set so that we can put start if necessary
        if(!verts.contains(start)) {    
            newVerts.add(start);
        }
        Iterator<V> itr = newVerts.iterator();
        HashMap<Edge, Path> hm = new HashMap<Edge, Path>();
        while(itr.hasNext()) {                                //go through the new set of vertices
            V v = itr.next();
            if (v == null) throw new IllegalArgumentException();
            Set<V> outgoing = new HashSet<V>();
            Iterator<V> i2 = newVerts.iterator();
            while (i2.hasNext()) {
                V v2 = i2.next();                            //create a new path if none exists between the two nodes and put in hashset
                if(!v.equals(v2)){
                    //if(g.connected(v, v2) == null) {
                        Path p = dijkstra.shortestPath(g, v, v2);
                        Edge E = new Edge(p.src(), p.dest());
                        completeG.addEdge(new WeightedEdge(p.src(), p.dest(), p.pathWeight()));
                        hm.put(E, p);
                    //}
                }
            }
        }
        Stack<V> stack2 = new Stack<V>();
        k = kruskal.spanningTree(completeG);
        Stack<V> s = DFS(start, stack2);
        
        while(!s.isEmpty()){
            retList.add(s.pop());
        }
        
        List<V> retList2 = new ArrayList();

        for(int i = retList.size()-1; i >= 0; i++) {
            retList2.add(retList.get(i));
        }

        return retList2;
        //throw new RuntimeException ("You need to implement this method");
    }
    
    
    public Stack<V> DFS(V start, Stack stack) {
        Set<WeightedEdge<V>> s = k.outgoingEdges(start);
        PriorityQueue<V> pq = new PriorityQueue<V>();
        Iterator<WeightedEdge<V>> itr = s.iterator();
        while(itr.hasNext()) {
            pq.add(itr.next().dest());
        }
        while(!pq.isEmpty()) {
            V v = pq.poll();
            stack.add(v);
            DFS(v, stack);
        }
        return stack;
    }
    
    
    /*public void DFS(Graph k, V start, Set newSet, Stack stack) {
        Set s = k.outgoingEdges(start);
        Set verts = new HashSet();
        Iterator itr = k.outgoingNeighbors(start).iterator();
        while(itr.hasNext()){
            E e = itr.next();
            verts.add(e.dest());
        }
        while(!verts.isEmpty()) {
            Iterator i2 = verts.iterator();
            V minV = (V) i2.next();
            while (i2.hasNext()) {
                V v2 = (V) i2.next();
                if (v2.compareTo(minV) < 0) {
                    minV = v2;
                }
            }
            stack.add(minV);
            verts.remove(minV);
        }
        DFS(k, minV, newSet, stack);
    }*/
    
    private class Node<V> {
        boolean visited;
        V vertex;
        
        public Node(V vertex) {
            this.vertex = vertex;
            visited = false;
        }
        
        public void setVisit(boolean visited) {
            this.visited = visited;
        }
    }
}
